package style.Leetcode.初级算法.array.array_20220730_2_只出现一次的数字;

import java.util.HashSet;

/**
 *
 * 只出现一次的数字
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 输入: [2,2,1]
 * 输出: 1
 *
 * 输入: [4,1,2,1,2]
 * 输出: 4
 */
public class Solution {
    /**
     *  思路1：
     *      位运算（相同为0 不同为1）
     *      1^1 = 0
     *      1^0 = 1
     *      0^1 = 1
     */
    public int singleNumber1(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }

    /**
     *  思路2：
     *     set
     *
     */
    public int singleNumber2(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int index = 0; index < nums.length; index++) {
            if (!set.add(nums[index])) {
                set.remove(nums[index]);
            }
        }
        return (int) set.toArray()[0];

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int res1 = solution.singleNumber1(new int[]{2,2,1});
        int res2 = solution.singleNumber2(new int[]{2,2,1});
        System.out.println(res2);
    }
}
